package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author shiminghui
 * @date 2025/2/1 16:24
 * @description: TODO
 */
public class _008_递归 {
    @Test
    public void test01() {
        int factorial = factorial(5);
        System.out.println(factorial);
    }

    @Test
    public void test02() {
        reversePrint("abcde", 5);
    }

    @Test
    public void test03() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int binarySearch = binarySearch(arr, 10, 0, arr.length);
        System.out.println(binarySearch);
    }


    @Test
    public void test04() {
        int[] arr = {1, 4, 3, 6, 2, 34, 6, 2, 1, 5};
        bubbleSort(arr, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    @Test
    public void test05() {
        int[] arr = {1, 4, 3, 6, 2, 34, 6, 2, 1, 5};
        insertSort(arr, 0);
        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    @Test
    public void test06() {
        System.out.println(fibonacci(10));
    }

    @Test
    public void test07() {
        System.out.println(rabbit(10));
    }

    @Test
    public void test08() {
        int[] cache = new int[10 + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        System.out.println(fibonacci(10, cache));
    }

    static LinkedList<Integer> a = new LinkedList<>();

    // 阶乘
    public int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    //反向打印字符串
    public void reversePrint(String str, int index) {
        if (index == 0) {
            return;
        }
        System.out.print(str.charAt(index - 1));
        reversePrint(str, index - 1);
    }

    // 递归二分
    public int binarySearch(int[] arr, int target, int left, int right) {
        if (left >= right) {
            return -1;
        }
        int mid = (left + right) >>> 1;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid);
        }
    }


    /**
     * 递归冒泡排序
     *
     * @param arr 数组
     * @param n   数组长度-1
     */
    public void bubbleSort(int[] arr, int n) {
        if (n == 0) {
            return;
        }
        int flag = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = i;  // 记录最后一次交换位置，若最后一次交换位置是1，则说明数组已经有序，不需要再继续排序
            }
        }

        bubbleSort(arr, n - 1);
    }


    // 递归插入排序，维护一个排列好的数组，每次插入一个元素，找到插入位置，然后插入，然后继续维护一个排列好的数组，直到数组全部排序完成
    public void insertSort(int[] arr, int n) {// n 是未排序的数组的下边界
        if (n == arr.length) {
            return;
        }
        int temp = arr[n];
        for (int i = n - 1; i >= 0; i--) {
            if (temp < arr[i]) {
                arr[i + 1] = arr[i];
            } else {
                if (i + 1 == n) { // 说明最右侧就是插入位置，即其本身，不用再赋值
                    break;
                }
                arr[i + 1] = temp;
                break;
            }
        }
        insertSort(arr, n + 1);
    }

    // 斐波那契数列(多路递归)
    public int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // 不死神兔问题，n是月份
    // 第n月的兔子是第n-1月兔子的数量加上n-1月生小兔子的数量，而第n-1月生小兔子的数量是第n-1月大兔子的数量，第n-1月大兔子的数量是第n-2月所有兔子的数量
    // 第n月的兔子是第n-1月兔子数量加上n-2月大兔子的数量。
    // 即f(n) = f(n-1) + f(n-2)
    public int rabbit(int n) {
        if (n == 1 || n == 2) {
            return 2;
        }
        return rabbit(n - 1) + rabbit(n - 2);
    }

    // 青蛙跳楼梯问题， 一次跳1阶或者2阶
    public int jumpFloor(int target) {
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }

    // 斐波那契数列(单路递归)，记忆优化
    public int fibonacci(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }
        return cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
    }
    static LinkedList<Integer> b = new LinkedList<>();

    // 汉诺塔问题，3根柱子，实践性代码
    static LinkedList<Integer> c = new LinkedList<>();

    @Test
    public void test09() {
        int[] cache = new int[10];
        Arrays.fill(cache, -1);
        System.out.println(hanoi(10, cache));
        System.out.println(Arrays.toString(cache));
    }

    // 汉诺塔问题,3根柱子,原理性代码 f(n) = 2*f(n-1)+1
    public int hanoi(int n, int cache[]) {
        if (n == 1) {
            return 1;
        }
        if (cache[n - 1] == -1) {
            cache[n - 1] = 2 * hanoi(n - 1, cache) + 1;
        }
        return cache[n - 1];
    }

    @Test
    public void test10() {
        init(a, 5);
        print();
        move(5, a, b, c);
    }

    private void init(LinkedList<Integer> linkedList, int n) {
        for (int i = 0; i < n; i++) {
            linkedList.addFirst(i + 1);
        }
    }

    private void move(int n, LinkedList<Integer> from, LinkedList<Integer> to, LinkedList<Integer> other) {
        if (n == 0) {
            return;
        }
        move(n - 1, from, other, to);
        other.addLast(from.removeLast());
        print();
        move(n - 1, to, from, other);
    }

    private void print() {
        System.out.println(a.toString());
        System.out.println(b.toString());
        System.out.println(c.toString());
        System.out.println("======================");
    }


    // 打印 n阶杨辉三角
    public void printYangHuiTriangle(int n) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            res.add(list);
            // 添加第i行的元素
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                } else {
                    list.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
        }
        for (List<Integer> list : res) {
            System.out.println(list.toString());
        }
    }

    @Test
    public void test11() {
        printYangHuiTriangle(5);
    }


    //使用递归的方法，实现杨辉三角某一行某一个的值
    public int getYangHuiTriangle(int i, int j) {
        if (i == 0 || j == 0 || i == j) {
            return 1;
        }
        return getYangHuiTriangle(i - 1, j - 1) + getYangHuiTriangle(i - 1, j);
    }

    @Test
    public void test12() {
        System.out.println(getYangHuiTriangle(4, 2));
    }

    // 打印一个杨辉三角
    public void printYangHuiTriangle2(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", getYangHuiTriangle(i, j));
            }
            System.out.println();
        }
    }

    //打印空格
    public void printSpace(int n, int i) {
        int num = (n - i - 1) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    @Test
    public void test13() {
        printYangHuiTriangle2(5);
    }

    // 用二维数组优化
    public int getYangHuiTriangle1(int i, int j, int[][] arr) {
        if (arr[i][j] != 0) {
            return arr[i][j];
        }

        if (i == 0 || j == 0 || i == j) {
            arr[i][j] = 1;
            return arr[i][j];
        }

        arr[i][j] = getYangHuiTriangle1(i - 1, j - 1, arr) + getYangHuiTriangle1(i - 1, j, arr);
        return arr[i][j];
    }

    @Test
    public void test14() {
        int n = 5;
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", getYangHuiTriangle1(i, j, arr));
            }
            System.out.println();
        }
    }

    //使用一维数组记录法实现杨辉三角
    public void printYangHuiTriangle3(int n, int[] arr, int index) {
        if (index == n) {
            return;
        }
        for (int i = index; i > 0; i--) {
            arr[i] = arr[i] + arr[i - 1];
        }
        System.out.println(Arrays.toString(arr));
        printYangHuiTriangle3(n, arr, ++index);
    }

    @Test
    public void test15() {
        int n = 5;
        int[] arr = new int[n];
        arr[0] = 1;
        printYangHuiTriangle3(n, arr, 0);
    }





}
